<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>~/ntl-11.4.2/doc/ZZXFactoring.cpp.html</title>
<meta name="Generator" content="Vim/8.0">
<meta name="plugin-version" content="vim7.4_v2">
<meta name="syntax" content="cpp">
<meta name="settings" content="use_css,pre_wrap,no_foldcolumn,expand_tabs,prevent_copy=">
<meta name="colorscheme" content="macvim">
<style type="text/css">
<!--
pre { white-space: pre-wrap; font-family: monospace; color: #000000; background-color: #ffffff; }
body { font-family: monospace; color: #000000; background-color: #ffffff; }
* { font-size: 1em; }
.String { color: #4a708b; }
.PreProc { color: #1874cd; }
.Constant { color: #ff8c00; }
.Comment { color: #0000ee; font-style: italic; }
.Type { color: #008b00; font-weight: bold; }
-->
</style>

<script type='text/javascript'>
<!--

-->
</script>
</head>
<body>
<pre id='vimCodeElement'>

<span class="Comment">/*</span><span class="Comment">****************************************************************************\</span>

<span class="Comment">MODULE: ZZXFactoring</span>

<span class="Comment">SUMMARY:</span>

<span class="Comment">Routines are provided for factoring in ZZX.</span>

<span class="Comment">See IMPLEMENTATION DETAILS below for a discussion of the algorithms used,</span>
<span class="Comment">and of the flags available for selecting among these algorithms.</span>

<span class="Comment">\****************************************************************************</span><span class="Comment">*/</span>

<span class="PreProc">#include </span><span class="String">&lt;NTL/ZZX.h&gt;</span>
<span class="PreProc">#include </span><span class="String">&lt;NTL/pair_ZZX_long.h&gt;</span>

<span class="Type">void</span> SquareFreeDecomp(vec_pair_ZZX_long&amp; u, <span class="Type">const</span> ZZX&amp; f);
<span class="Type">const</span> vector(pair_ZZX_long SquareFreeDecomp(<span class="Type">const</span> ZZX&amp; f);

<span class="Comment">// input is primitive, with positive leading coefficient.  Performs</span>
<span class="Comment">// square-free decomposition.  If f = prod_i g_i^i, then u is set to a</span>
<span class="Comment">// lest of pairs (g_i, i).  The list is is increasing order of i, with</span>
<span class="Comment">// trivial terms (i.e., g_i = 1) deleted.</span>


<span class="Type">void</span> MultiLift(vec_ZZX&amp; A, <span class="Type">const</span> vec_zz_pX&amp; a, <span class="Type">const</span> ZZX&amp; f, <span class="Type">long</span> e,
               <span class="Type">long</span> verbose=<span class="Constant">0</span>);

<span class="Comment">// Using current value p of zz_p::modulus(), this lifts the</span>
<span class="Comment">// square-free factorization a mod p of f to a factorization A mod p^e</span>
<span class="Comment">// of f.  It is required that f and all the polynomials in a are</span>
<span class="Comment">// monic.</span>



<span class="Type">void</span> SFFactor(vec_ZZX&amp; factors, <span class="Type">const</span> ZZX&amp; f, <span class="Type">long</span> verbose=<span class="Constant">0</span>, <span class="Type">long</span> bnd=<span class="Constant">0</span>);
vec_ZZX SFFactor(<span class="Type">const</span> ZZX&amp; f, <span class="Type">long</span> verbose=<span class="Constant">0</span>, <span class="Type">long</span> bnd=<span class="Constant">0</span>);

<span class="Comment">// input f is primitive and square-free, with positive leading</span>
<span class="Comment">// coefficient.  bnd, if not zero, indicates that f divides a</span>
<span class="Comment">// polynomial h whose Euclidean norm is bounded by 2^{bnd} in absolute</span>
<span class="Comment">// value.  This uses the routine SFCanZass in zz_pXFactoring and then</span>
<span class="Comment">// performs a MultiLift, followed by a brute-force search for the</span>
<span class="Comment">// factors.  </span>

<span class="Comment">// A number of heuristics are used to speed up the factor-search step.</span>
<span class="Comment">// See &quot;implementation details&quot; below.</span>


<span class="Type">void</span> factor(ZZ&amp; c,
            vec_pair_ZZX_long&amp; factors,
            <span class="Type">const</span> ZZX&amp; f,
            <span class="Type">long</span> verbose=<span class="Constant">0</span>,
            <span class="Type">long</span> bnd=<span class="Constant">0</span>);

<span class="Comment">// input f is is an arbitrary polynomial.  c is the content of f, and</span>
<span class="Comment">// factors is the facrorization of its primitive part.  bnd is as in</span>
<span class="Comment">// SFFactor.  The routine calls SquareFreeDecomp and SFFactor.</span>

<span class="Type">void</span> mul(ZZX&amp; x, <span class="Type">const</span> vec_pair_ZZX_long&amp; a);
ZZX mul(<span class="Type">const</span> vec_pair_ZZX_long&amp; a);
<span class="Comment">// multiplies polynomials, with multiplcities.</span>




<span class="Comment">/*</span><span class="Comment">****************************************************************************\</span>

<span class="Comment">IMPLEMENTATION DETAILS</span>

<span class="Comment">To factor a polynomial, first its content is extracted, and it is</span>
<span class="Comment">made squarefree.  This is typically very fast.</span>

<span class="Comment">Second, a simple hack is performed: if the polynomial is of the</span>
<span class="Comment">form g(x^l), then an attempt is made to factor g(k^m),</span>
<span class="Comment">for divisors m of l, which can in some cases greatly simplify</span>
<span class="Comment">the factorization task.</span>
<span class="Comment">You can turn this &quot;power hack&quot; on/off by setting the following variable</span>
<span class="Comment">to 1/0:</span>

<span class="Comment">   extern thread_local long ZZXFac_PowerHack;  // initial value = 1</span>


<span class="Comment">Third, the polynomial is factored modulo several</span>
<span class="Comment">small primes, and one small prime p is selected as the &quot;best&quot;.</span>
<span class="Comment">You can choose the number of small primes that you want to use</span>
<span class="Comment">by setting the following variable:</span>

<span class="Comment">   extern thread_local long ZZXFac_InitNumPrimes;  // initial value = 7</span>

<span class="Comment">Fourth, The factorization mod p is &quot;lifted&quot; to a factorization mod p^k</span>
<span class="Comment">for a sufficiently large k.  This is done via quadratic Hensel</span>
<span class="Comment">lifting.  Despite &quot;folk wisdom&quot; to the contrary, this is much</span>
<span class="Comment">more efficient than linear Hensel lifting, especially since NTL</span>
<span class="Comment">has very fast polynomial arithmetic.</span>

<span class="Comment">After the &quot;lifting phase&quot; comes the &quot;factor recombination phase&quot;.</span>
<span class="Comment">The factorization mod p^k may be &quot;finer&quot; than the true factorization</span>
<span class="Comment">over the integers, hence we have to &quot;combine&quot; subsets of modular factors</span>
<span class="Comment">and test if these are factors over the integers.</span>

<span class="Comment">There are two basic strategies:  the &quot;Zassenhaus&quot; method</span>
<span class="Comment">and the &quot;van Hoeij&quot; method.</span>

<span class="Comment">The van Hoeij method:</span>

<span class="Comment">The van Hoeij method is fairly new, but it is so much better than</span>
<span class="Comment">the older, Zassenhaus method, that it is now the default.</span>
<span class="Comment">For a description of the method, go to Mark van Hoeij's home page:</span>

<span class="Comment">   <a href="http://www.openmath.org/~hoeij/">http://www.openmath.org/~hoeij/</a></span>

<span class="Comment">The van Hoeij method is not really a specific algorithm, but a general</span>
<span class="Comment">algorithmic approach: many parameters and strategies have to be selected</span>
<span class="Comment">to obtain a specific algorithm, and it is a challenge to</span>
<span class="Comment">make all of these choices so that the resulting algorithm works</span>
<span class="Comment">fairly well on all input polynomials.</span>

<span class="Comment">Set the following variable to 1 to enable the van Hoeij method,</span>
<span class="Comment">and to 0 to revert to the Zassenhaus method:</span>

<span class="Comment">   extern thread_local long ZZXFac_van_Hoeij; // initial value = 1</span>

<span class="Comment">Note that the &quot;power hack&quot; is still on by default when using van Hoeij's</span>
<span class="Comment">method, but we have arranged things so that the &quot;power hack&quot; strategy </span>
<span class="Comment">is abandoned if it appears to be too much a waste of time.</span>
<span class="Comment">Unlike with the Zassenhaus method, using the &quot;power hack&quot; method with</span>
<span class="Comment">van Hoeij can sometimes be a huge waste of time if one is not careful.</span>



<span class="Comment">The Zassenhaus method:</span>

<span class="Comment">The Zassenhaus method is essentially a brute-force search, but with</span>
<span class="Comment">a lot of fancy &quot;pruning&quot; techniques, as described in the paper</span>
<span class="Comment">[J. Abbott, V. Shoup, P. Zimmermann, &quot;Factoring in Z[x]: the searching phase&quot;,</span>
<span class="Comment">ISSAC 2000].</span>

<span class="Comment">These heuristics are fairly effective, and allow one to easily deal</span>
<span class="Comment">with up to around 30-40 modular factors, which is *much* more</span>
<span class="Comment">than other Zassenhaus-based factorizers can deal with; however, after this, </span>
<span class="Comment">the exponential behavior of the algorithm really starts to dominate.</span>

<span class="Comment">The behaviour of these heuristics can be fine tuned by</span>
<span class="Comment">setting the following global variables:</span>

<span class="Comment">   extern thread_local long ZZXFac_MaxNumPrimes;  // initial value = 50</span>
<span class="Comment">   // During the factor recombination phase, if not much progress</span>
<span class="Comment">   // is being made, occasionally more &quot;local&quot; information is </span>
<span class="Comment">   // collected by factoring f modulo another prime.</span>
<span class="Comment">   // This &quot;local&quot; information is used to rule out degrees </span>
<span class="Comment">   // of potential factors during recombination.</span>
<span class="Comment">   // This value bounds the total number of primes modulo which f </span>
<span class="Comment">   // is factored.</span>

<span class="Comment">   extern thread_local long ZZXFac_MaxPrune;  // initial value = 10</span>
<span class="Comment">   // A kind of &quot;meet in the middle&quot; strategy is used</span>
<span class="Comment">   // to prune the search space during recombination.</span>
<span class="Comment">   // For many (but not all) polynomials, this can greatly</span>
<span class="Comment">   // reduce the running time.</span>
<span class="Comment">   // When it does work, there is a time-space tradeoff:</span>
<span class="Comment">   // If t = ZZXFac_MaxPrune, the running time will be reduced by a factor near</span>
<span class="Comment">   // 2^t, but the table will take (at most) t*2^(t-1) bytes of storage.</span>
<span class="Comment">   // Note that ZZXFac_MaxPrune is treated as an upper bound on t---the</span>
<span class="Comment">   // factoring algorithm may decide to use a smaller value of t for</span>
<span class="Comment">   // a number of reasons.</span>



<span class="Comment">\****************************************************************************</span><span class="Comment">*/</span>
</pre>
</body>
</html>
<!-- vim: set foldmethod=manual : -->
